1. Field
The present disclosure pertains to the field of information processing, and, more specifically, to the field of optimizing program code.
2. Description of Related Art
The performance of an information processing system may be improved by optimizing the program code that runs on the system. One technique for optimizing program code is to eliminate instructions that are not necessary for correct program execution. For example, program code may be optimized by identifying and eliminating “dead” instructions. A dead instruction is a producer or other instruction that does not produce data used by a consumer, where a producer is an instruction that produces data and a consumer is an instruction that uses data.
Dead instructions may be found in a sequence or stream of instructions within a program that is always executed in its entirety, with no branch or other execution path into the instruction stream after the first instruction or out of the instruction stream before the last instruction. In other words, the instruction stream has a single entry point, at the beginning, and a single exit point, at the end. Producers in such an instruction stream may produce data that is stored for use by consumers either inside or outside the stream. Any instruction that does not produce data that is available for use by instructions outside the stream, or does not produce data that is used, directly or indirectly, to produce data that is available for use outside the stream is a dead instruction. An example of a dead instruction is an instruction that writes data to a register or other storage location, but before the data is used by another instruction, the register or other storage location is overwritten by another instruction inside the stream.
Typically, dead instructions are identified by analyzing an instruction stream in reverse order of execution. A register or other storage element that has been written to by a producer inside the stream and is readable by a consumer outside the stream after execution of the stream is referred to as a “live-out” register. The last producer to write data to a live-out register is not a dead instruction, because it is assumed that there is a consumer of the data outside the stream. If any such last producer is also a consumer of any prior producer inside the stream, then each such prior producer is also not a dead instruction. If each such prior producer is also a consumer of any other prior producer inside the stream, then each such other prior producer is also not a dead instruction, and so on. Therefore, an instruction stream may be analyzed in reverse to first identify whether an instruction is a last producer, then to identify whether an instruction is a producer of data for a last producer, and so on. After such a complete backward pass, any leftover instructions may then be identified as dead instructions.